package br.ufpe.abaco.ParserGen.parser;

import java.io.FileOutputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;

import br.ufpe.abaco.ParserGen.CompilerException;
import br.ufpe.abaco.ParserGen.lexer.Token;

/**
 *  Esta classe representa o parser. Atua como uma fachada para o gerador de parser.
 *
 *@author     Monique Monteiro e Pablo Sampaio
 *Criado em 30 de Outubro de 2002
 */
public class Parser  implements java.io.Serializable  {
	public static final byte BACKTRACKING_PARSING = 1;
	public static final byte PSEUDO_PARALELL_PARSING = 2;
	public static final int MAX_BACKTRACKS = 4000;
	private LRTable table;
	private BNFGrammar grammar;
	private SemanticAction[] semActions;
	private StringBuffer log = new StringBuffer();
	private static final boolean DEBUG = true;
	private static final String PARSER_FILE = "PARSER.TXT";
	private static final String LANGUAGE_FILE = "LANGUAGE.TXT";

	HashMap<String,Integer> initialStates = new HashMap<String,Integer>();
	
	/**
	 * Construtor da classe.
	 * 
	 * @param grammar	a gram�tica da linguagem (n�o aumentada).
	 */
	public Parser(BNFGrammar grammar) {
		this(grammar, false);
	}

	/**
	 *  Construtor da classe.
	 *
	 *@param  grammar  			a gram�tica da linguagem (n�o aumentada).
	 *@param  saveGrammarLog	<code>true</code> se dever ser gerado um arquivo com as
	 *							informa��es da gram�tica, <code>false</code> caso
	 *							contr�rio.
	 */
	public Parser(BNFGrammar grammar, boolean saveGrammarLog) {
        //System.out.println("INSTANCIOU O PARSER");
		Vector<Production> start = grammar.augment();
		Production[] prods = grammar.getAllProductions();
		for (NonTerminalSymbol n : grammar.startSymbols()) {
			initialStates.put(n.getName(), initialStates.size());
		}
		int prodsLength = prods.length;
		this.semActions = new SemanticAction[prodsLength];

		for (int i = 0; i < prodsLength; i++) {
			this.semActions[i] = prods[i].getSemanticAction();
		}

		this.table = new LRTable(grammar, start, saveGrammarLog);
		this.grammar = grammar;

		//System.out.println("Number of ambiguities: " + table.ambiguities);

		if (saveGrammarLog) {
			//imprime a tabela em um arquivo
			//table.print();
			//imprime a gramatica em outro arquivo
			saveGrammarLog();
		}
		
		//System.out.println("FIM INSTANCIACAO DO PARSER");

	}

	public String getLog() {
		return this.log.toString();
	}

	public String getGrammarLog() {
		return this.table.getLog();
	}

	/**
	 * Gera um arquivo de log com os detalhes da linguagem ( gram�tica, conjuntos de itens,
	 * ambiguidades, etc.).
	 *
	 * @see LRTable.getLog()
	 */
	public void saveGrammarLog() {
/*		try {
			PrintWriter pw =
				new PrintWriter(new FileOutputStream(LANGUAGE_FILE));
			pw.print(getGrammarLog());
			pw.close();
		} catch (IOException ioe) {
			ioe.printStackTrace();
		}*/
	}

	
    public Object parse(Token[] sentence, byte parsingProcess, boolean debug) throws CompilerException {
		if (initialStates.size()!=1) {
			RuntimeException ex = new RuntimeException("System error: Can't chooce default startSymbol because there is more that one symbol\nPlease contact the developers.");
			ex.printStackTrace();
			throw ex;
		}
		return parse(sentence,initialStates.keySet().iterator().next(),parsingProcess,debug);
	}
	
	/**
	 * Realiza o parsing.
	 *
	 * @param sentence		    o conjunto de lexemas correspondentes � entrada
	 * @param parsingProcess    indica o processo de parsing, que pode ser utilizando
	 * 						    backtracking (BACKTRACKING_PARSING) ou um algoritmo de 
	 * 						    parsers pseudoparalelos (PSEUDO_PARALELL_PARSING)1.
	 * @param debug			    <code>true</code>, se informacoes de debug devem ser 
	 * 						    incluidas, <code>false</code> caso contrario.
	 * @return Object		    a(s) �rvore(s) sint�tica(s) encontradas, ou 
	 * 						    <code>null</code> caso a entrada seja vazia.
	 * @throws ParsingException se ocorrer erro de parsing
	 */
	public Object parse(Token[] sentence, String nonTerminal,byte parsingProcess, boolean debug)
		throws CompilerException {
		Object result = null;
		int initialState;
		if (initialStates.containsKey(nonTerminal))
			initialState = initialStates.get(nonTerminal);
		else
			return null;

		if (sentence != null && sentence.length > 0) {
			try {
				if (parsingProcess == BACKTRACKING_PARSING) {
					result = backtrackingParse(sentence,initialState, debug);
				} else if (parsingProcess == PSEUDO_PARALELL_PARSING) {
					result = paralellParse(sentence,initialState);
				} else {
					throw new IllegalArgumentException("parametro parsingProcess invalido");
				}
			} finally {
				saveParserLog();
			}
		}

		return result;
	}

	/**
	 *  Este metodo implementa um parser que utilizar backtrackng para resolver ambiguidades.
	 *
	 * @param  sentence  the sentence to be parsed
	 * @param  debug     true se devem ser geradas informa��es de log. OBS.: Estou
	 *                   usando este parametro para evitar constru��o/concatena��o
	 *                   de strings desnecess�ria
	 * @return           the sentence's parsing tree
	 */
	public Object backtrackingParse(Token[] sentence, int initialState, boolean debug)
		throws CompilerException {
        //System.out.println("CHEGOU AO PARSER");
		boolean accepted = false;
		boolean backtrack = false;
		int numBacktracks = 0;
		log.setLength(0);
		int sentenceIndex = 0;
		int state;
		ParserStackElement currentStack =
			new ParserStackElement(initialState, null, null);
		Object result = null;
		int errorPosition = -1;

		/*
		 *  Guarda os n�veis do bracktracking, ou seja as m�ltiplas possibilidades
		 *  que pode testar
		 */
		BacktrackingState[] levels = new BacktrackingState[10000];
		BacktrackingState level = null;
		int levelIndex = -1;
		TerminalSymbol symbol = null;
		String lexema = null;
		ParserAction action = null;
		ParserAction[] actions = new ParserAction[1];
		TerminalSymbol[] symbols = null;
		boolean readNewSymbol = true;

		while (!accepted && numBacktracks <= MAX_BACKTRACKS) {
			if (!backtrack) {
				symbols = sentence[sentenceIndex].getMatchings();

				if (readNewSymbol) {
					symbol = symbols[0];
				}

				lexema = sentence[sentenceIndex].getValue();
				state = currentStack.state;
				//actions = this.table.getActionEntry(state, symbol, actions);
				actions = this.table.getActionEntry(state, symbol, new ParserAction[1]);
				action = actions[0];

				if (actions.length > 1 || symbols.length > 1) {
					levels[++levelIndex] =
						new BacktrackingState(
							sentenceIndex,
							actions,
							symbols,
							lexema,
							currentStack);

					if (debug) {
						log.append(
							"\n<<Ambiguity - Level " + levelIndex + ">>\n");

						for (int i = 0; i < actions.length; i++) {
							log.append(
								"Action " + i + ": " + actions[i].print());
						}

						log.append("\n\n");
					}
				}
			} else {
				boolean foundLevel = false;

				while (!foundLevel && levelIndex >= 0) {
					level = levels[levelIndex];

					if (level.nextAction < level.actions.length) {
						//tenta a proxima acao (sem mudar o simbolo)
						foundLevel = true;
						symbol = level.terminals[level.nextTerminal];
						currentStack = level.top;
						sentenceIndex = level.sentenceIndex;
						lexema = level.lexema;
						action = level.actions[level.nextAction];
						//prepara para uma possivel tentativa futura
						level.nextAction++;

						if (debug) {
							log.append(
								"Level "
									+ levelIndex
									+ " - Trying action: "
									+ action.print());
						}
					} else {
						//tenta o proximo simbolo terminal
						level.nextTerminal++;

						if (level.nextTerminal < level.terminals.length) {
							foundLevel = true;
							symbol = level.terminals[level.nextTerminal];
							currentStack = level.top;
							sentenceIndex = level.sentenceIndex;
							lexema = level.lexema;
							actions =
								this.table.getActionEntry(
									currentStack.state,
									symbol,
									actions);
							level.actions = actions;
							action = actions[0];
							level.nextAction = 1;
						} else {
							//neste ponto, "foundLevel" eh "false" (continua no laco)
							levels[levelIndex] = null;
							//retira o nivel da pilha
							levelIndex--;
							//tenta o proximo nivel
						}
					}
				} //end while
				if (!foundLevel) {
					//desiste
					//System.out.println("ERRO NO GERADOR DE PARSER");

					StringBuffer str = new StringBuffer();
					while (errorPosition<sentence.length && str.length()<20) {
							str.append(sentence[errorPosition++].getValue());
							str.append(" ");
					}
					if (errorPosition<sentence.length) str.append(" ...");
					   throw new ParsingException(str.toString());
				} else {
					backtrack = false;
					numBacktracks++;

					if (debug) {
						log.append("<< Backtrack >>\n");

					}
				}
			}
			//end if-else
			if (debug) {
				log.append(
					">> Symbol: "
						+ symbol
						+ '\n'
						+ ">> Text: "
						+ lexema
						+ '\n'
						+ "   => Action: "
						+ action.print()
						+ '\n');
			}
			if (action instanceof ShiftAction) {
				/*
				 *  empilha o estado
				 */
				currentStack =
					new ParserStackElement(
						((ShiftAction) action).state,
						symbol.getAction().act(sentence[sentenceIndex]),
						currentStack,
						symbol);
				/*
				 *  l� o proximo lexema
				 */
				sentenceIndex++;
				/*
				 *  indica que o proximo simbolo a ser lido eh o primeiro simbolo que casou
				 *  com o proximo lexema
				 */
				readNewSymbol = true;
			} else if (action instanceof ReduceAction) {
				Production production = ((ReduceAction) action).production;
				NonTerminalSymbol left = production.getLeftSide();
				ParserStackElement next = currentStack;
				int length = production.getRightSide().length;
				Object[] values = new Object[length];

				//desempilha
				for (int j = 0; j < length; j++) {
					values[length - j - 1] = next.value;
					next = next.next;
				}
				state = next.state;
				SemanticAction semAction = this.semActions[production.index];
				currentStack =
					new ParserStackElement(
						this.table.getGotoEntry(state, left),
						this.semActions[production.index].act(values),
						next,
						left);
				if (semAction instanceof BacktrackingAction) {
					backtrack = true;
				}
				readNewSymbol = false;
			} else if (action instanceof ErrorAction) {
				if (sentenceIndex > errorPosition) {
					errorPosition = sentenceIndex;
				}
				backtrack = true;
				readNewSymbol = false;
			} else if (action instanceof AcceptAction) {
				accepted = true;
				result = currentStack.value;
			}
			//fecha if
		} //fecha while

		if (numBacktracks > MAX_BACKTRACKS) {
			StringBuffer str = new StringBuffer();
			while (errorPosition<sentence.length && str.length()<20) {
					str.append(sentence[errorPosition++].getValue());
					str.append(" ");
			}
			if (errorPosition<sentence.length) str.append(" ...");
			   throw new ParsingException(str.toString());
//			throw new ParsingException(
//				sentence[errorPosition],
//				"Backtracks limits reached!!!");
		}

		return result;
	}

	/**
	 *  Algoritmo de parser LR com pseudo-paralelismo. Retorna todas as
	 *  respostas possiveis (para o caso de haver ambiguidades na gramatica) ate
	 *  um limite de 5000 respostas. Se houver mais respostas, elas sao
	 *  descartadas.
	 *
	 *  @param  sentence  conjunto de pares (tokens, lexema) sobre o qual ser�
	 *      			  realizado o parsing.
	 *  @return           conjunto de possiveis arvores sintaticas.
	 */
	public Object[] paralellParse(Token[] sentence,int initialState) throws CompilerException {
		boolean accepted = false;
		ParserStackElement[] thisSweep = new ParserStackElement[10000];
		ParserStackElement[] nextSweep = new ParserStackElement[10000];
		Object[] respostas = new Object[5000];
		ParserStackElement[] temp;
		int nextSymbol = 0;
		int thisIndex = -1;
		//ultimo indice valido de thisSweep
		int nextIndex = 0;
		//ultimo indice valido de nextSweep
		int numRespostas = 0;
		TerminalSymbol[] terminais;
		String lexema;
		nextSweep[0] = new ParserStackElement(initialState, null, null);

		while (nextIndex >= 0) {
			temp = thisSweep;
			thisSweep = nextSweep;
			nextSweep = temp;
			thisIndex = nextIndex;
			nextIndex = -1;
			terminais = sentence[nextSymbol].getMatchings();
			lexema = sentence[nextSymbol].getValue();
			nextSymbol++;
			ParserStackElement parserAtual;
			ParserAction[] actions = new ParserAction[1];
			TerminalSymbol symbol;
			int stateAux;

			while (thisIndex >= 0) {
				//System.out.println("(" + thisIndex + ") " + thisSweep[thisIndex]);
				parserAtual = thisSweep[thisIndex];
				thisIndex--;
				//retira parserAtual de thisSweep
				/*
				 *  Testa todos os terminais com os quais o lexema casou.
				 */
				for (int i = 0; i < terminais.length; i++) {
					symbol = terminais[i];
					actions =
						this.table.getActionEntry(
							parserAtual.state,
							symbol,
							actions);
					//System.out.println(" =>Simbolo: " + symbol + ", valor: " + lexema);
					/*
					 *  Testa todas as possiveis acoes da tabela de acoes.
					 */
					for (int k = 0; k < actions.length; k++) {
						ParserAction action = actions[k];
						//System.out.println("  =>A��o: " + action);
						if (action instanceof ShiftAction) {
							stateAux = ((ShiftAction) action).state;
							nextSweep[++nextIndex] =
								new ParserStackElement(
									stateAux,
									symbol.getAction().act(sentence[nextSymbol]),
									parserAtual,
									symbol);
							//System.out.println("SHIFT POR: " + lexema);
						} else if (action instanceof ReduceAction) {
							Production production =
								((ReduceAction) action).production;
							ParserStackElement prox = parserAtual;
							int length = production.getRightSide().length;
							Object[] values = new Object[length];
							Object result;

							for (int j = 0; j < length; j++) {
								values[length - j - 1] = prox.value;
								//preenche o array "values" de
								//tras pra frente
								prox = prox.next;
								//equivalente a um "pop" na pilha
							}

							stateAux =
								this.table.getGotoEntry(
									prox.state,
									production.getLeftSide());
							//System.out.println("    Proximo estado: " + stateAux);
							//result = production.getSemanticAction().act(values); //comparar a performance
							result =
								this.semActions[production.index].act(values);
							//destas duas abordagens
							thisSweep[++thisIndex] =
								new ParserStackElement(
									stateAux,
									result,
									prox,
									production.getLeftSide());
							/*System.out.println("REGRA: " + production);
							 System.out.println("SIMBOLO LIDO: " + symbol);
							     System.out.println("LEXEMA: " + lexema + "\n");*/
						} else if (action instanceof AcceptAction) {
							accepted = true;
							if (numRespostas < respostas.length) {
								respostas[numRespostas++] = parserAtual.value;
							}
						}
					} //fecha for
				} //fecha for
			} //fecha while
		} //fecha while

		Object[] respostasAux = new Object[numRespostas];

		for (int r = 0; r < numRespostas; r++) {
			respostasAux[r] = respostas[r];
		}

		return respostasAux;
	}

	/**
	 * Gera um arquivo de log com os passos executados pelo parser.	 
	 */
	public void saveParserLog() {
/*		try {
			PrintWriter pw = new PrintWriter(new FileOutputStream(PARSER_FILE));
			pw.print(getLog());
			pw.close();
		} catch (IOException ioe) {
			ioe.printStackTrace();
		}
*/	}

	/**
	 *  Representa um elemento da pilha de parsing
	 *
	 *@author     Monique Monteiro
	 *@created    30 de Outubro de 2002
	 */
	class ParserStackElement {
		private final ParserStackElement next;
		private final Object value;
		private final int state;
		private GrammarSymbol symbol;
		//apenas para debug

		ParserStackElement(
			int estado,
			Object valor,
			ParserStackElement next,
			GrammarSymbol simbolo) {
			this.state = estado;
			this.value = valor;
			this.next = next;
			this.symbol = simbolo;
		}

		ParserStackElement(int estado, Object valor, ParserStackElement next) {
			this.state = estado;
			this.value = valor;
			this.next = next;
		}

		public int size() {
			if (next == null) {
				return 1;
			} else {
				return (1 + next.size());
			}
		}

		public String toString() {
			String next =
				(this.next == null) ? "" : (this.next.toString() + " ");
			String simb =
				(this.symbol == null) ? "" : (this.symbol.toString() + " ");
			String val =
				(this.value == null)
					? ""
					: ("<<" + this.value.toString() + ">> ");
			return next + simb + val + this.state;
		}
	}

	/**
	 *  Representa uma "fotografia" da pilha de parsers atual do backtracking
	 *  Guarda o pr�ximo �ndice da entrada a ser lido, o array de a��es
	 *  possiveis e a pr�xima a��o a ser tentada neste array caso a a��o atual
	 *  leve a um erro.
	 *
	 *@author     Monique Monteiro
	 *@created    30 de Outubro de 2002
	 */
	class BacktrackingState {
		/*
		 *  o topo da pilha
		 */
		private final ParserStackElement top;
		/*
		 *  pr�xima posi��o da senten�a a ser lida
		 */
		private final int sentenceIndex;
		/*
		 *  a string que casou com os terminais
		 */
		private final String lexema;
		/*
		 *  possiveis simbolos terminais reconhecidos
		 */
		private final TerminalSymbol[] terminals;
		/*
		 *  proximo terminal a ser tentado
		 */
		private int nextTerminal;
		/*
		 *  array de a��es poss�veis para o simbolo terminals[nextTerminal]
		 */
		private ParserAction[] actions;
		/*
		 *  posi��o da pr�xima a��o do array "actions" a ser testada
		 */
		private int nextAction;

		BacktrackingState(
			int sentenceIndex,
			ParserAction[] actions,
			TerminalSymbol[] symbols,
			String lexValue,
			ParserStackElement topo) {
			this.sentenceIndex = sentenceIndex;
			this.actions = actions;
			this.nextAction = 1;
			// a acao zero eh tentada imediatamente (sem backtracking)
			this.terminals = symbols;
			this.nextTerminal = 0;
			// o terminal permanece fixo ate todas as acoes serem tentatadas
			this.lexema = lexValue;
			this.top = topo;
		}
	}

	public void printTable() {
		this.table.print();
	}
}
